package LeetCode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LC_047_PermutationsII {
    public static void main(String[] args) {

    }

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new LinkedList<>();
            List<Integer> tmpList = new LinkedList<>();
            boolean[] visited = new boolean[nums.length];

            Arrays.sort(nums);
            solve(nums, res, tmpList, visited);
            return res;
        }

        private void solve(int[] nums, List<List<Integer>> res, List<Integer> item, boolean[] visited) {
            int length = nums.length;
            
            if (item.size() == length) {
                res.add(new LinkedList<>(item));
                return;
            }

            for (int i = 0; i < length; i++) {
                while (i > 0 && i < length && nums[i] == nums[i - 1] && !visited[i - 1])
                    i++;
                if (i == length)
                    return;

                if (visited[i])
                    continue;

                item.add(nums[i]);
                visited[i] = true;

                solve(nums, res, item, visited);

                visited[i] = false;
                item.remove(item.size() - 1);
            }
        }
    }
}
